package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 127. 单词接龙
 * 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
 * <p>
 * 每一对相邻的单词只差一个字母。
 * 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
 * sk == endWord
 * 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 * 输出：5
 * 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
 * 示例 2：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
 * 输出：0
 * 解释：endWord "cog" 不在字典中，所以无法进行转换。
 */
public class LadderLength {

    int ans = Integer.MAX_VALUE;
    Set<String> used = new HashSet<>();

    /**
     * 回溯法，思路可以
     * TODO 但是容易超时 没有跑通
     *
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }

        back(beginWord, endWord, wordList);
        return ans = ans == Integer.MAX_VALUE ? 0 : ans + 1;
    }

    public void back(String beginWord, String endWord, List<String> wordList) {
        if (beginWord.equals(endWord)) {
            ans = Math.min(ans, used.size());
            return;
        }

        for (int i = 0; i < wordList.size(); i++) {
            String next = wordList.get(i);
            if (used.add(next) && close(beginWord, next)) {
                back(next, endWord, wordList);
                used.remove(next);
            }
        }
    }


    public boolean close(String a, String b) {
        char[] a1 = a.toCharArray();
        char[] b1 = b.toCharArray();
        int res = 0;

        int n = a1.length;

        for (int i = 0; i < n; i++) {
            if (a1[i] != b1[i]) {
                res++;
            }
        }
        return res == 1;
    }
}
